/*
自己选择的路 ,跪着也要走完。朋友们 , 虽然这个世界日益浮躁起来,只
要能够为了当时纯粹的梦想和感动坚持努力下去 , 不管其它人怎么样,我
们也能够保持自己的本色走下去。
To the world , you will be a person , but to a person , you
will be the world .                               ——AKPower
*/
#include <iostream>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <vector>
#include <map>
#include <queue>
#include <cstdio>
#include <string>
#include <stack>
#include <set>
#define IOS ios::sync_with_stdio(false), cin.tie(0)
using namespace std;
typedef long long ll;
const ll INF = 1000000000000000;
const int maxn = 5e5 + 10;
ll n,m;
struct node{
    ll y,next_s,val;
}e[maxn*2];
struct edge
{
    ll x, y, val;
}line[maxn];

ll dis[2][maxn];
ll head[maxn],cnt;
bool vis[maxn];
map<string, ll> mp;

void init(){
    memset(head, -1, sizeof(head));
    cnt = 0;
}

void add(ll x,ll y,ll val){
    e[cnt].y = y;
    e[cnt].val = val;
    e[cnt].next_s = head[x];
    head[x] = cnt++;
}
priority_queue<pair<ll, ll>> p;

int main()
{
    string t1, t2;
    ll val;
    while(cin>>n>>m){
        init();
        mp.clear();
        for (ll i=1;i<=n;i++){
            vis[i] = false;
            dis[0][i] = INF;
            dis[1][i] = INF;
        }
        ll id = 1;
        for (ll i=1;i<=m;i++){
            cin >> t1 >> t2 >> val;
            if(mp.find(t1)==mp.end()){
                mp[t1] = id++;
            }
            if(mp.find(t2)==mp.end()){
                mp[t2] = id++;
            }
            ll x = mp[t1];
            ll y = mp[t2];
            line[i].x = x;
            line[i].y = y;
            line[i].val = val;
            add(x, y, val);
            add(y, x, val);
        }
        cin >> t1 >> t2;
        if(t1==t2){
            cout << 0 << endl;
            continue;
        }
        if(mp.find(t1)==mp.end()||mp.find(t2)==mp.end()){
            cout << -1 << endl;
            continue;
        }
        ll st = mp[t1];
        ll en = mp[t2];
        for (ll i=head[st];i!=-1;i=e[i].next_s){
            ll y = e[i].y;
            ll v = e[i].val;
            dis[0][y] =min(dis[0][y],v);
        }
        dis[0][st] = 0;
        p.push(make_pair(0, st));
        while(!p.empty()){
            ll x = p.top().second;
            p.pop();
            if(vis[x])
                continue;
            vis[x] = true;
            for (ll i = head[x]; i != -1;i=e[i].next_s){
                ll y = e[i].y;
                ll v = e[i].val;
                if (dis[0][y]>=dis[0][x] + v){
                    dis[0][y] = dis[0][x] + v;
                    p.push(make_pair(-dis[0][y], y));
                }
            }
        }
        for (ll i=1;i<=n;i++){
            vis[i] = false;
        }
        for (ll i=head[en];i!=-1;i=e[i].next_s){
            ll y = e[i].y;
            ll v = e[i].val;
            // dis[1][y] = v;
            dis[1][y] =min(dis[1][y],v);
        }
        dis[1][en] = 0;
        p.push(make_pair(0, en));
        while(!p.empty()){
            ll x = p.top().second;
            p.pop();
            if(vis[x])
                continue;
            vis[x] = true;
            for (ll i = head[x]; i != -1;i=e[i].next_s){
                ll y = e[i].y;
                ll v = e[i].val;
                if (dis[1][y] >=dis[1][x] + v){
                    dis[1][y] = dis[1][x] + v;
                    p.push(make_pair(-dis[1][y], y));
                }
            }
        }
        // for (ll i=1;i<=n;i++){
        //     cout << dis[0][i] << " ";
        // }
        // cout << endl;
        // for (ll i=1;i<=n;i++){
        //     cout << dis[1][i] << " ";
        // }
        // cout << endl;
        ll ans = INF;
        for (ll i=1;i<=m;i++){
            ll x = line[i].x;
            ll y = line[i].y;
            ll v = line[i].val;
            ans = min(ans, min(dis[0][x] + dis[1][y], dis[0][y] + dis[1][x]) + (v ) / 2);
        }
        if(ans==INF){
            cout << -1 << endl;
        }
        else
            cout << ans << endl;
    }
    return 0;
}